A point cloud is a set of points in three-dimensional (3-D) space that represents surfaces of one or more objects (e.g., in the physical environment). Each point of a point cloud is typically associated with coordinates (e.g., an x-axis coordinate, a y-axis coordinate, and a z-axis coordinate) of a coordinate system (e.g., a Cartesian coordinate system). Point clouds are often created by 3-D scanners that employ light detection and ranging (LIDAR) technology. However, other remote sensing technology, such as stereoscopic imagery, may be employed to create point clouds. Modern point clouds often contain millions or even billions of points. By use of large numbers of individual points, is point clouds may represent objects with a high level of precision. With such precision, a point cloud may be used to capture narrow elongated objects, such as transmission lines, railroad tracks, road markings and the like. Such narrow elongated objects are referred to herein generally as “linear features.”
In addition to coordinates, each point of a point cloud may be associated with certain properties. In some cases, for instance when a point cloud is obtained using LIDAR technology, each point in the point cloud may also be associated with a reflectance intensity (e.g., such that each point has an x-axis coordinate, a y-axis coordinate, a z-axis coordinate, and a reflectance intensity). The reflectance intensity can be used to discriminate between objects. For example, road markings usually reflect light more than the bare asphalt of a road surface. By looking to the reflectance intensity of points, a system may be able to discriminate between the road markings and the bare road surface, despite the two being part of the same geometric surface.
When visually displayed, points of a point cloud may be colored (e.g., in gray-scale or with red-green-blue (RGB) values) based on one or more properties. For example, points may be colored based on their reflectance intensity, for example, to visually distinguish between road markings and the bare asphalt of a road surface. FIG. 1 is a view 100 of an example point cloud that has been colored based on reflectance intensity.
Similar to pixels of a two-dimensional (2-D) image, points of point clouds often cannot be effectively used in engineering applications in their native form. While a point cloud may provide a precise picture of objects in a scene, the points themselves are generally not suited for direct use in analyzing the scene. For example, points generally cannot be directly used in computing geometric properties (e.g., length, surface area, volume, etc.) of objects. To have a form that can be more easily analyzed, a line-based model may be reconstructed from a point cloud. A line-based model generally represents objects using one or more polylines, i.e. continuous lines composed of one or more line segments. For example, a polyline may represent a linear feature (e.g., a road marking, a railroad track, a transmission line, etc.). The polylines of the line-based model, rather than the underlying points, can be subject to the desired analysis.
Creating polylines to represent linear features in a point cloud may be challenging. Some systems employ a manual approach. However, creating polylines manually may present problems. One problem that stems from the non-solid nature of point clouds is that objects located behind a region of interest may become visible. When viewed from afar, a point cloud may appear solid. However, when viewed closer it becomes apparent that the point cloud is really composed of discrete points with spaces in between. If a user zooms in on a particular region of interest in a point cloud, points describing objects located behind the region of interest may become visible through the spaces between points in the foreground.
FIG. 2 is a view 200 of an example point cloud showing an overpass 210 having road markings 220 as viewed from afar. In FIG. 2, the road markings 220 on the overpass 210, including the road markings near reference dot 230 on the overpass's surface, are clearly visible.
FIG. 3 is an example of an enlarged view 300 of the point cloud of FIG. 2. As can be seen, after zooming in on a portion of the overpass, the road markings near reference dot 230 begin to vanish. Worse still, some road markings 310 from another roadway below the overpass, located near reference dot 320, may start to become visible, confusing the view.
Another problem that stems from the non-solid nature of point clouds is that it may be difficult to select the correct points to “snap” to. During manual creation of a polyline, a user typically “snaps” to points, to establish a position of the line in 3-D space. However, given that the point cloud is not solid, it is often difficult to select the correct points. A point may appear to be a part of the desired object when the point cloud is viewed from one perspective, but it may become obvious that the point is not part of the desired object (e.g., is part of an object above or below the desired object), if the point is cloud is viewed from another perspective.
FIG. 4 is an example near top down view 400 of a point cloud showing a polyline 410 that has been drawn in an attempt to model a road marking on an overpass. From a near top down perspective, it appears that the polyline 410 is a good representation of the road marking. As in the other examples, reference dot 230 is on the overpass's surface, while reference dot 320 is located on the roadway below.
FIG. 5 is an example of an isometric view 500 of the point cloud of FIG. 4. From the isometric perspective, it becomes clear that one end of the polyline 410 is not even near the road marking on the overpass's surface (near reference dot 230). Instead, one endpoint of the polyline 410 is actually near a roadway passing below the overpass (near reference dot 320)
In addition to these problems stemming from the non-solid nature of point clouds, further problems are often encountered when trying to manually create polylines to represent linear features. One such problem is that a user may be burdened having to select a large number of points to accurately model a linear features. As mentioned above, a point cloud may include millions or billions of points, and therefore can describe linear features in great detail. To accurately represent some linear features (e.g., curving linear features, such as transmission lines), a polyline may have to be “snapped” to a large number of individual points to capture the contours of the curves. This may require hours of tedious manual operations.
Yet another problem may stem from occlusion of some parts of linear features by other objects. For example, referring back to the example in FIG. 3, it can be seen that the road marking near reference dot 310 is partly hidden by the points that represent the overpass. To fully see the occluded linear features, a user may have to clip the point cloud. For example, in reference to FIG. 3, a user may have to clip the portion of the point cloud that represents the overpass. However, this requires extra operations and therefore decreases productivity.
Accordingly, there is a need for a technique that can extract polylines from a point cloud semi-automatically, to allow for fast and precise modeling of linear features of a is point cloud.